package greedy_algorithm;

import java.util.Arrays;

/**
 * 救生艇 - 881
 */
public class 救生艇 {
    public static void main(String[] args) {
        int[] people = {3, 8, 4, 9, 2, 2, 7, 1, 6, 10, 6, 7, 1, 7, 7, 6, 4, 4, 10, 1};
        int limit = 10;//11
        int res = new 救生艇().numRescueBoats(people, limit);
        System.out.println(res);
    }

    /**
     * 计算最少需要多少艘船来救援所有人，每艘船有一个重量限制。
     *
     * @param people 整型数组，表示每个人的体重
     * @param limit  整数，表示每艘船的重量限制
     * @return 返回一个整数，表示最少需要的船的数量
     */
    public int numRescueBoats(int[] people, int limit) {
        // 获取人数
        int n = people.length;

        // 初始化轻体重者和重体重者的索引
        int light = 0, heavy = n - 1;

        // 初始化计数器，记录所需船只数量
        int res = 0;

        // 对人员体重进行排序，便于后续处理
        Arrays.sort(people);

        // 当轻体重者索引小于等于重体重者索引时，继续处理
        while (light <= heavy) {
            // 如果最轻和最重的人一起不会超重，则轻体重者上船
            if (people[light] + people[heavy] <= limit) {
                light++;
            }

            // 无论当前组合是否超重，最重的人都会乘坐此船
            heavy--;

            // 船次增加
            res++;
        }

        // 返回所需最少船的数量
        return res;
    }
}
